/* eslint-disable no-restricted-syntax */
/* eslint-disable no-lonely-if */
/* eslint-disable no-console */
/* eslint-disable no-param-reassign */
/* eslint-disable class-methods-use-this */
import { RedBlackTreeNode } from './redBlackTreeNode'

export const NIL: RedBlackTreeNode<any, any> = new RedBlackTreeNode<any, any>(
	undefined,
	undefined,
	undefined
)

/**
 * 红黑树，
 * 性质：
 * 1. 每个结点或是红的，或是黑的。
 * 2. 根结点是黑的
 * 3. 每个空(NIL)结点是黑的
 * 4. 如果一个结点是红的，则它的两个儿子都是黑的。
 * 5. 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
 */
export class RedBlackTree<K, V> {
	root: RedBlackTreeNode<K, V> = NIL

	/**
	 * 左旋转，将一个结点置换到它的左子结点的位置。
	 *
	 * 需要维护二叉查找树的性质（左小右大）。
	 *
	 * leftRotate(x) 和 rightRotate(right)互为逆操作。
	 *
	 * ```txt
	 * left < x < a < right < b
	 *
	 * From:
	 * x
	 * |-> left
	 * |-> right
	 * |   |-> a
	 * |   |-> b
	 *
	 * To:
	 * right
	 * |-> x
	 * |   |-> left
	 * |   |-> a
	 * |-> b
	 * ```
	 *
	 * @param node the node
	 */
	leftRotate(node: RedBlackTreeNode<K, V>): void {
		if (node === NIL) {
			return
		}
		const originalRight = node.rightChild

		// 结点的右子结点 <- 原来右节点的左子结点。
		node.rightChild = originalRight.leftChild

		// 原来的右节点的左子节点 <- 原结点。
		if (originalRight.leftChild !== NIL) {
			originalRight.leftChild.parent = node
		}

		// 原来的右节点置换到原结点的位置。
		originalRight.parent = node.parent

		// 调整原父节点。
		if (node.parent === NIL) {
			// case: 原结点是根节点，
			this.root = originalRight
		} else if (node === node.parent.leftChild) {
			// case: 原结点是父节点的左子节点。
			node.parent.leftChild = originalRight
		} else {
			// case: 原结点是父节点的右子节点。
			node.parent.rightChild = originalRight
		}

		originalRight.leftChild = node
		node.parent = originalRight
	}

	/**
	 * 右旋转，将一个结点置换到它的右子结点的位置。
	 *
	 * 需要维护二叉查找树的性质（左小右大）。
	 *
	 * rightRotate(x) 和 leftRotate(left)互为逆操作。
	 *
	 * ```txt
	 * a < left < b < x < right
	 *
	 * From:
	 * x
	 * |-> left
	 * |   |-> a
	 * |   |-> b
	 * |-> right
	 *
	 * To:
	 * left
	 * |-> a
	 * |-> x
	 * |   |-> b
	 * |   |-> right
	 * ```
	 * @param node the node
	 */
	rightRotate(node: RedBlackTreeNode<K, V>): void {
		if (node === NIL) {
			return
		}
		const originalLeft = node.leftChild

		// 结点的左子结点 <- 原来左节点的右子结点。
		node.leftChild = originalLeft.rightChild

		// 原来的左节点的右子节点 <- 原结点。
		if (originalLeft.rightChild !== NIL) {
			originalLeft.rightChild.parent = node
		}

		// 原来的左节点置换到原结点的位置。
		originalLeft.parent = node.parent

		// 调整原父节点。
		if (node.parent === NIL) {
			// case: 原结点是根节点，
			this.root = originalLeft
		} else if (RedBlackTree.isLeftChild(node)) {
			// case: 原结点是父节点的左子节点。
			node.parent.leftChild = originalLeft
		} else {
			// case: 原结点是父节点的右子节点。
			node.parent.rightChild = originalLeft
		}

		originalLeft.rightChild = node
		node.parent = originalLeft
	}

	delete(node: RedBlackTreeNode<K, V>): RedBlackTreeNode<K, V> {
		if (node === NIL) {
			return NIL
		}

		let y: RedBlackTreeNode<K, V> = NIL
		let x: RedBlackTreeNode<K, V> = NIL
		if (node.leftChild === NIL || node.rightChild === NIL) {
			y = node
		} else {
			y = this.successor(node) as RedBlackTreeNode<K, V>
		}

		if (y.leftChild !== NIL) {
			x = y.leftChild
		} else {
			x = y.rightChild
		}

		if (x !== NIL) {
			x.parent = y.parent
		}

		if (y.parent === NIL) {
			this.root = x
		} else if (RedBlackTree.isLeftChild(y)) {
			y.parent.leftChild = x
		} else {
			y.parent.rightChild = x
		}

		if (y !== node) {
			y.copyAttributesTo(node)
		}

		if (y.isBlack) {
			this.deleteFixUp(x)
		}

		return y
	}

	private deleteFixUp(node: RedBlackTreeNode<K, V>): void {
		if (node === NIL) {
			return
		}
		while (node !== this.root && node.isBlack) {
			if (RedBlackTree.isLeftChild(node)) {
				let w = node.parent.rightChild
				if (w.isRed) {
					w.isBlack = true
					node.parent.isRed = true
					this.leftRotate(node.parent)
					w = node.parent.rightChild
				}
				if (w.leftChild.isBlack && w.rightChild.isBlack) {
					w.isRed = true
					node = node.parent
				} else {
					if (w.rightChild.isBlack) {
						w.leftChild.isBlack = true
						w.isRed = true
						this.rightRotate(w)
						w = node.parent.rightChild
					}
					w.isRed = node.parent.isRed
					node.parent.isBlack = true
					w.rightChild.isBlack = true
					this.leftRotate(node.parent)
					node = this.root
				}
			} else {
				// same as then clause with "right" and "left" exchanged
				let w = node.parent.leftChild
				if (w.isRed) {
					w.isBlack = true
					node.parent.isRed = true
					this.rightRotate(node.parent)
					w = node.parent.leftChild
				}
				if (w.rightChild.isBlack && w.leftChild.isBlack) {
					w.isRed = true
					node = node.parent
				} else {
					if (w.leftChild.isBlack) {
						w.rightChild.isBlack = true
						w.isRed = true
						this.leftRotate(w)
						w = node.parent.leftChild
					}
					w.isRed = node.parent.isRed
					node.parent.isBlack = true
					w.leftChild.isBlack = true
					this.rightRotate(node.parent)
					node = this.root
				}
			}
		}
		node.isBlack = true
	}

	insert(key: K, value: V): void {
		// create the node and configure parent properties
		const node = new RedBlackTreeNode<K, V>(key, value, NIL)

		if (this.root === NIL) {
			this.root = node
		} else {
			// Find the insert parent
			let targetParent: RedBlackTreeNode<K, V> = NIL
			let x = this.root
			while (x !== NIL) {
				targetParent = x
				if (key < x.key) {
					x = x.leftChild
				} else {
					x = x.rightChild
				}
			}

			node.parent = targetParent
			if (node.key < targetParent.key) {
				targetParent.leftChild = node
			} else {
				targetParent.rightChild = node
			}
		}

		// red
		node.isRed = true
		this.insertFixUp(node)
	}

	/**
	 * 保证红黑树的性质
	 * @param node the node
	 */
	private insertFixUp(node: RedBlackTreeNode<K, V>): void {
		// 由于node是红色，所以父是红色违反了规则
		while (node.parent.isRed) {
			if (RedBlackTree.isLeftChild(node.parent)) {
				const y = node.parent.parent.rightChild
				if (y.isRed) {
					// case: 1
					node.parent.isBlack = true
					y.isBlack = true
					if (node.parent.parent !== NIL) {
						node.parent.parent.isRed = true
					}
					node = node.parent.parent
				} else {
					// case 2 or 3
					if (RedBlackTree.isRightChild(node)) {
						// case 2 node 为右子
						node = node.parent
						this.leftRotate(node)
					}
					// case 3 node 为左子
					node.parent.isBlack = true
					node.parent.parent.isRed = true
					this.rightRotate(node.parent.parent)
				}
			} else {
				const y = node.parent.parent.leftChild
				if (y.isRed) {
					node.parent.isBlack = true
					y.isBlack = true
					if (node.parent.parent !== NIL) {
						node.parent.parent.isRed = true
					}
					node = node.parent.parent
				} else {
					if (RedBlackTree.isLeftChild(node)) {
						node = node.parent
						this.rightRotate(node)
					}
					node.parent.isBlack = true
					node.parent.parent.isRed = true
					this.leftRotate(node.parent.parent)
				}
			}
		}
		this.root.isBlack = true
	}

	static isLeftChild(node: RedBlackTreeNode<any, any>): boolean {
		return node === node.parent.leftChild
	}

	static isRightChild(node: RedBlackTreeNode<any, any>): boolean {
		return node === node.parent.rightChild
	}

	tree(node?: RedBlackTreeNode<K, V>, level?: number): string {
		if (node === undefined && level === undefined) {
			node = this.root
			level = 0
		}

		let result: string = ''
		// output level
		let levelText: string = ''
		if (level > 0) {
			if (level > 1) {
				levelText = '│   '.repeat(level - 1)
			}
			levelText += '├── '
		}

		// output node
		result = `${levelText}${this.renderTreeNodeColor(node)}`

		// case: null node -> do not output children
		if (node === NIL) {
			return result
		}

		// output children
		if (node.leftChild !== NIL || node.rightChild !== NIL) {
			result += `\n${this.tree(node.leftChild, level + 1)}`
			result += `\n${this.tree(node.rightChild, level + 1)}`
		}

		return result
	}

	private renderTreeNodeColor(node: RedBlackTreeNode<K, V>): string {
		if (node === NIL) {
			return '(nil)'
		}

		if (node.isBlack) {
			return (node.value as unknown) as string
		}

		return `\x1b[31m${node.value}\x1b[0m`
	}

	maximum(node: RedBlackTreeNode<K, V> = this.root): RedBlackTreeNode<K, V> {
		if (node === NIL) {
			return node
		}

		while (node.rightChild !== NIL) {
			node = node.rightChild
		}

		return node
	}

	minimum(node: RedBlackTreeNode<K, V> = this.root): RedBlackTreeNode<K, V> {
		if (node === NIL) {
			return node
		}

		while (node.leftChild !== NIL) {
			node = node.leftChild
		}

		return node
	}

	/**
	 * Search 的非递归版本
	 * @param key the key
	 */
	search(key: K): RedBlackTreeNode<K, V> {
		let node = this.root
		while (node !== NIL && node.key !== key) {
			if (key < node.key) {
				node = node.leftChild
			} else {
				node = node.rightChild
			}
		}

		if (key === node.key) {
			return node
		}
		return undefined
	}

	/**
	 * 返回指定结点在中序遍历中的后继结点
	 * @param node the node
	 */
	successor(node: RedBlackTreeNode<K, V>): RedBlackTreeNode<K, V> {
		if (node.rightChild !== NIL) {
			return this.minimum(node.rightChild)
		}

		let y = node.parent
		while (y !== NIL && node === y.rightChild) {
			node = y
			y = y.parent
		}

		return y
	}

	/**
	 * 返回指定索引的结点。
	 * 也是第最小i个的结点。
	 * @param index the index, return index-nd node
	 * @param node the node, optional the root node
	 */
	select(
		index: number,
		node: RedBlackTreeNode<K, V> = this.root
	): RedBlackTreeNode<K, V> {
		const r = node.leftChild.size + 1
		if (index === r) {
			return node
		}

		if (index < r) {
			return this.select(index, node.leftChild)
		}

		return this.select(index, node.rightChild)
	}

	/**
	 * 返回指定结点的顺序排名。
	 * @param node the node, optional the root node
	 */
	getRank(node: RedBlackTreeNode<K, V> = this.root): number {
		let rank = node.leftChild.size + 1
		let tnode: RedBlackTreeNode<K, V> = node
		while (tnode === this.root) {
			if (RedBlackTree.isRightChild(tnode)) {
				rank += tnode.parent.leftChild.size + 1
			}
			tnode = tnode.parent
		}

		return rank
	}

	/**
	 * 返回指定结点在中序遍历中的前序结点
	 * @param node the node
	 */
	predecessor(node: RedBlackTreeNode<K, V>): RedBlackTreeNode<K, V> {
		if (node.leftChild !== NIL) {
			return this.maximum(node.leftChild)
		}

		let y = node.parent
		while (y !== NIL && node === y.leftChild) {
			node = y
			y = y.parent
		}

		return y
	}

	walkThrough(
		node: RedBlackTreeNode<K, V>,
		callback: (node: RedBlackTreeNode<K, V>) => void
	): void {
		if (node.leftChild !== NIL) {
			this.walkThrough(node.leftChild, callback)
		}
		callback(node)
		if (node.rightChild !== NIL) {
			this.walkThrough(node.rightChild, callback)
		}
	}

	validate(): string[] {
		let errors: string[] = []
		let err = this.validateRootIsBlack()
		if (err) {
			errors = errors.concat(err)
		}

		err = this.validateLeftSmallerRightBigger()
		if (err) {
			errors = errors.concat(err)
		}

		err = this.validateRedNodeHasTwoBlack()
		if (err) {
			errors = errors.concat(err)
		}

		// return
		return errors
	}

	private validateLeftSmallerRightBigger(): string[] {
		const errors: string[] = []
		this.walkThrough(this.root, (node: RedBlackTreeNode<K, V>) => {
			if (node === NIL) {
				return
			}
			if (node.leftChild !== NIL) {
				if (node.leftChild.key > node.key) {
					errors.push(`the left node of (${node.key}) must be small`)
				}
			}
			if (node.rightChild !== NIL) {
				if (node.rightChild.key < node.key) {
					errors.push(`the right node of (${node.key}) must be bigger`)
				}
			}
		})
		return errors
	}

	private validateRootIsBlack(): string[] {
		if (this.root.isRed) {
			return ['The root node must be black']
		}
		return []
	}

	private validateRedNodeHasTwoBlack(): string[] {
		const errors: string[] = []
		this.walkThrough(this.root, (node: RedBlackTreeNode<K, V>) => {
			if (node === NIL || node.isBlack) {
				return
			}
			if (node.leftChild.isRed) {
				errors.push(`the left node of (${node.key}) must be black`)
			}
			if (node.rightChild.isRed) {
				errors.push(`the right node of (${node.key}) must be black`)
			}
		})
		return errors
	}
}
